package com.cb2.algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/minimum-absolute-difference-in-bst/">二叉搜索树的最小绝对差(Minimum Absolute Difference in BST)</a>
 * <p>给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。</p>
 * <p>差值是一个正数，其数值等于两值之差的绝对值。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [4,2,6,1,3]
 *                  4
 *                /  \
 *               2    6
 *             /  \
 *            1    3
 *      输出：1
 *
 * 示例 2：
 *      输入：root = [1,0,48,null,null,12,49]
 *                  1
 *                /  \
 *               0   48
 *                  /  \
 *                 12  49
 *      输出：1
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目范围是 [2, 10^4]</li>
 *     <li>0 <= Node.val <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/11 11:50
 */
public class LC0530MinimumAbsoluteDifferenceInBST_S {

    static class Solution {
        public int getMinimumDifference(TreeNode root) {
            int prevNodeVal = -1;
            int minimumDiff = Integer.MAX_VALUE;

            // 二叉搜索树的中序遍历是有序的，用后一个减去前一个求绝对值
            Deque<TreeNode> helper = new LinkedList<>();
            while (!helper.isEmpty() || root != null) {
                while (root != null) {
                    helper.addLast(root);
                    root = root.left;
                }
                TreeNode currNode = helper.removeLast();
                if (prevNodeVal != -1) {
                    minimumDiff = Math.min(minimumDiff, Math.abs(currNode.val - prevNodeVal));
                }
                prevNodeVal = currNode.val;
                root = currNode.right;
            }
            return minimumDiff;
        }

        private int minimumDiff = Integer.MAX_VALUE;
        private int prevNodeVal = -1;

        public int getMinimumDifference2(TreeNode root) {
            dfs(root);
            return minimumDiff;
        }

        /**
         * 中序遍历，左根右
         */
        private void dfs(TreeNode currNode) {
            if (currNode == null) {
                return;
            }
            dfs(currNode.left);
            if (prevNodeVal != -1) {
                minimumDiff = Math.min(minimumDiff, Math.abs(currNode.val - prevNodeVal));
            }
            prevNodeVal = currNode.val;
            dfs(currNode.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(4);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(6);
        root1.left.left = new TreeNode(1);
        root1.left.right = new TreeNode(3);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(0);
        root2.right = new TreeNode(48);
        root2.right.left = new TreeNode(12);
        root2.right.right = new TreeNode(49);

        Solution solution = new Solution();
        System.out.println(solution.getMinimumDifference(root1));
        System.out.println(solution.getMinimumDifference(root2));
    }
}
